/*
 * @lc app=leetcode.cn id=239 lang=cpp
 *
 * [239] 滑动窗口最大值
 */

// @lc code=start
class Solution
{
private:
    //使用deque来建立单调队列
    class Mydeque
    {
    public:
        deque<int> que;
        void push(int value)
        {
            //将元素插入到队列中 如果该元素大于末尾元素 出列 直到当前元素比队尾小
            while (!que.empty() && value > que.back())
            {
                que.pop_back();
            }
            que.push_back(value);
        }
        void pop(int value)
        {
            if (!que.empty() && value == que.front())
            {
                que.pop_front();
            }
        }
        int front()
        {
            return que.front();
        }
    };

public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        Mydeque que;
        vector<int> res;
        //先将前k个元素入队
        for (int i = 0; i < k; i++)
        {
            que.push(nums[i]);
        }
        res.push_back(que.front()); //将前k个元素最大值加入res
        //滑动窗口
        for (int i = k; i < nums.size(); i++)
        {
            que.pop(nums[i - k]);       //删除初始元素
            que.push(nums[i]);          //插入下一个元素
            res.push_back(que.front()); //记录当前最大值
        }
        return res;
    }
};
// @lc code=end
